//
//  BSTree.swift
//  others
//
//  Created by lhc on 2024/8/26.
//

import Foundation

/// 二分搜索树
class BSTree<T: Comparable, E>: BinaryTree<T, E> {
    /// 添加key value的node
    func add(key: T, value: E?) {
        
        self.root = self.add(key: key, value: value, node: self.root)
    }
    
    private func add(key: T, value: E?, node: Node?) -> Node {
        guard let node = node else {
            self.size += 1
            return Node(key: key, value: value)
        }
        
        if key < node.key {
            node.left = self.add(key: key, value: value, node: node.left)
            return node
        }else if key > node.key {
            node.right = self.add(key: key, value: value, node: node.right)
            return node
        }
        // key == node.key
        node.value = value
        return node
    }
    
    /// 移除key值的node
    func remove(key: T) {
        // 如果返回值 == nil 那么不存在当前key 直接结束
        guard let _ = self.getWithKey(key) else {return}
        
        self.root = self.remove(key: key, node: self.root!)
    }
    
    private func remove(key: T, node: Node?) -> Node? {
        guard let node = node else {return nil}
        
        if key < node.key {
            node.left = self.remove(key: key, node: node.left)
            return node
        }else if key > node.key {
            node.right = self.remove(key: key, node: node.right)
            return node
        }else {
            // key = node.key
            // 就是删除当前node
            
            if node.left == nil {
                let right = node.right
                node.right = nil
                self.size -= 1
                return right
            }
            if node.right == nil {
                let left = node.left
                node.left = nil
                self.size -= 1
                return left
            }
            
            // 既有left 又有right
            // successor为node右子树最小值
            let successor = self.miniNode(node: node.right!)
            // 在node右子树上删除掉successor
            
            successor.right = self.remove(key: successor.key, node: node.right)
            successor.left = node.left
            
            node.left = nil
            node.right = nil
            
            return successor
        }
    }
    
}

 
